package ink.ykb.rpn;

/**
 * 双向链表
 */
public class LinkList<E> {
	
	private Link<E> first;
	
	private Link<E> last;

	public LinkList() {
		first = null;
		last = null;
	}
	
	public boolean isEmpty(){
		return first == null;
	}
	
	public void insertFirst(E data){
		Link<E> newLink = new Link<>(data);
		
		if(isEmpty()){
			last = newLink;
		}else{
			first.setPrevious(newLink);
		}
		newLink.setNext(first);
		first = newLink;
	}
	
	public void insertLast(E data){
		Link<E> newLink = new Link<>(data);
		
		if(isEmpty()){
			first = newLink;
		}else{
			last.setNext(newLink);
			newLink.setPrevious(last);
		}
		last = newLink;
	}
	
	public Link<E> deleteFirst(){
		if(isEmpty()){
			throw new RuntimeException("双向链表为空");
		}
		Link<E> temp = first;
		
		if(first.getNext() == null){
			last = null;
		}else{
			first.getNext().setPrevious(null);
		}
		first = first.getNext();
		return temp;
	}
	
	public Link<E> deleteLast(){
		if(isEmpty()){
			throw new RuntimeException("双向链表为空");
		}
		Link<E> temp = last;
		
		if(first.getNext() == null){
			first = null;
		}else{
			last.getPrevious().setNext(null);
		}
		last = last.getPrevious();
		return temp;
	}
	
	/**
	 * 在key之后插入数据
	 * @param key
	 * @param data
	 * @return
	 */
	public boolean insertAfter(E key,E data){
		if(isEmpty()){
			throw new RuntimeException("双向链表为空");
		}
		if(key == null || data == null){
			throw new RuntimeException("数据不能为空");
		}
		
		Link<E> current = first;
		while(!current.getData().equals(key)){
			current = current.getNext();
			if(current == null){
				return false;
			}
		}
		
		Link<E> newLink = new Link<>(data);
		if(current.equals(last)){
			newLink.setNext(null);
			last = newLink;
		}else{
			newLink.setNext(current.getNext());
			current.getNext().setPrevious(newLink);
		}
		newLink.setPrevious(current);
		current.setNext(newLink);
		return true;
	}
	
	public Link<E> deleteKey(E key){
		if(isEmpty()){
			throw new RuntimeException("双向链表为空");
		}
		
		Link<E> current = first;
		while(!current.getData().equals(key)){
			current = current.getNext();
			if(current == null){
				return null;
			}
		}
		
		if(current.equals(first)){
			first = current.getNext();
		}else{
			current.getPrevious().setNext(current.getNext());
		}
	
		if(current.equals(last)){
			last = current.getPrevious();
		}else{
			current.getNext().setPrevious(current.getPrevious());
		}
		
		return current;
	}
	
	public void displayForward(){
		System.out.println("List (first --> last)：");
		
		Link<E> current = first;
		while(current != null){
			System.out.println(current.toString());
			current = current.getNext();
		}
		System.out.println("");
	}
	
	public void displayBackward(){
		System.out.println("List (last --> first)：");
		
		Link<E> current = last;
		while(current != null){
			System.out.println(current.toString());
			current = current.getPrevious();
		}
		System.out.println("");
	}

    public Link<E> getFirst() {
      return first;
    }
  
    public Link<E> getLast() {
      return last;
    }
	
	
	
}
